package main

/*
当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。

给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

MyCalendarThree() 初始化对象。
int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。
 */

type SegmentNode struct {
	lt, rt *SegmentNode
	num, lazy int
}
func (node *SegmentNode) update(L, R, start, end int) {
	if start <= L && R <= end {
		node.num++; node.lazy++
		return
	}
	node.pushdown()
	mid := (L + R) >> 1
	if start <= mid {node.lt.update(L, mid, start, end)}
	if end > mid {node.rt.update(mid + 1, R, start, end)}
	node.pushup()
}
func (node *SegmentNode) pushup() {node.num = max(node.lt.num, node.rt.num)}
func (node *SegmentNode) pushdown() {
	if node.lt == nil {node.lt = new(SegmentNode)}
	if node.rt == nil {node.rt = new(SegmentNode)}
	if node.lazy == 0 {
		return
	}
	node.lt.num += node.lazy
	node.lt.lazy += node.lazy
	node.rt.num += node.lazy
	node.rt.lazy += node.lazy
	node.lazy = 0
}
func (node *SegmentNode) query(L, R, start, end int) (ans int) {
	if start <= L && R <= end {return node.num}
	node.pushdown()
	mid := (L + R) >> 1
	if start <= mid {ans = node.lt.query(L, mid, start, end)}
	if end > mid {ans = max(ans, node.rt.query(mid + 1, R, start, end))}
	return
}
func max(a, b int) int {
	if a > b {return a}
	return b
}
type MyCalendarThree struct {
	Root SegmentNode
}
func Constructor() MyCalendarThree {
	return MyCalendarThree{SegmentNode{}}
}
func (this *MyCalendarThree) Book(start int, end int) int {
	this.Root.update(0, 1e9, start, end - 1)
	return this.Root.num
	//return this.Root.query(0, 1e9, 0, 1e9)
}